TNotes.leetcode

Appearance

0859. 亲密字符串【简单】

0859. 亲密字符串【简单】 ​

1. 📝 题目描述 ​

  • 给你两个字符串 s 和 goal，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false。
  • 交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j，接着交换 s[i] 和 s[j] 处的字符。
  • 例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad"。

示例 1：

txt
输入：s = "ab", goal = "ba"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。

示例 2：

txt
输入：s = "ab", goal = "ab"
输出：false
解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。

示例 3：

txt
输入：s = "aa", goal = "aa"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。

提示：

  • 1 <= s.length, goal.length <= 2 * 10^4
  • s 和 goal 由小写英文字母组成

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {string} s
 * @param {string} goal
 * @return {boolean}
 */
var buddyStrings = function (s, goal) {
  // 长度不相等直接返回 false
  if (s.length !== goal.length) {
    return false
  }

  // 如果两个字符串相等，检查是否存在重复字符
  if (s === goal) {
    // 使用 Set 检查是否有重复字符
    const uniqueChars = new Set(s)
    return uniqueChars.size < s.length
  }

  // 找到所有不同的字符位置
  const diff = []
  for (let i = 0; i < s.length; i++) {
    if (s[i] !== goal[i]) {
      diff.push(i)
    }
  }

  // 必须恰好有两个不同的位置，且交换后相等
  return (
    diff.length === 2 &&
    s[diff[0]] === goal[diff[1]] &&
    s[diff[1]] === goal[diff[0]]
  )
}
  • 时间复杂度：O(n)，其中 n 是字符串长度，需要遍历一次字符串
  • 空间复杂度：O(1)，只使用了常数额外空间（Set 的大小最多为 26 个字母）
  • 算法思路：
    • 题目要求：判断两个字符串是否可以通过恰好交换两个字符位置变成相同字符串。
    • 我们分以下 3 种情况讨论：
      • 1️⃣ 先检查长度：如果两个字符串长度不相等，直接返回 false
      • 2️⃣ 再检查相等：如果两个字符串完全相同，只有当存在重复字符时才能满足条件（可以交换两个相同的字符）
      • 3️⃣ 最后查不同：找出所有不同的位置，必须恰好有 2 个不同位置，且交换后能使两个字符串相等

Discussions